Per poter analizzare il ragionamento matematico, è necessario innanzitutto individuare quali simboli e costrutti linguistici vengono usati. Scorrendo un testo di analisi matematica ci si imbatte in vari tipi di simboli.
Le lettere \(x\), \(y\), \(z\), … in genere designano numeri reali arbitrari, mentre le lettere \(k , m , n , \dots\) denotano numeri naturali. In ogni caso, il loro ruolo è quello di essere variabili, ovvero quello di indicare un generico numero anziché identificarne uno specifico.
Al contrario, certe lettere designano numeri ben specifici: sono cioè delle costanti. Per esempio la lettera \(\pi\) rappresenta un preciso numero reale, ovvero il rapporto tra la lunghezza del diametro e la lunghezza della circonferenza. Il suo valore è \(\pi = 3,14159 \dots\).
Alcuni simboli denotano operazioni tra numeri o particolari funzioni. Ad esempio, i simboli \(+\) e \(\cdot\) denotano le operazioni binarie di somma e prodotto, mentre \(\sqrt{.}\) indica la funzione “radice quadrata”.
Altri simboli denotano relazioni tra numeri, come il simbolo \(<\) che usiamo per indicare l’ordine tra i numeri.
Il simbolo \(=\), che denota l’uguaglianza, è anch’esso un simbolo per una relazione tra oggetti, ma il suo significato è fissato ed indipendente dal contesto: esso asserisce che l’oggetto scritto a sinistra del segno di uguale coincide con l’oggetto scritto a destra.
Vedremo che tutte queste tipologie di simboli giocheranno un ruolo fondamentale quando presenteremo la logica del prim’ordine.
Ci sono poi alcune espressioni che ricorrono in ogni testo matematico:
le particelle “non”, “e”, “o”
“se …allora …”
“…se e solo se …”
“c’è almeno un \(x\) tale che …”
“per ogni \(x\) …”.
Espressioni di questo genere le abbiamo anche ripetutamente incontrate nella nostra trattazione informale del concetto di dimostrazione (Sezione 1.1).
Per scrivere in modo non ambiguo i ragionamenti e le dimostrazioni introduciamo dei simboli che rappresentano questi costrutti linguistici, ovvero i connettivi
\(\neg\) \(\wedge\) \(\vee\) \(\rightarrow\) \(\leftrightarrow\)
ed i simboli di quantificatore
\(\exists\) \(\forall\)
I connettivi e i quantificatori si dicono costanti logiche. Vediamo il loro significato e alcune delle loro proprietà di base.
\(\neg\) denota la negazione e serve per affermare l’opposto di quanto asserisce l’affermazione a cui si applica.
Per esempio \[\neg ( x < y )\] significa che \(x\) non è minore di \(y\), ovvero che \(x \geq y\).
Data un’affermazione \(\mathrm{P}\), si ha sempre che \(\mathrm{P}\) è vera se e solo se \(\neg \mathrm{P}\) è falsa, e questo accade se e solo \(\neg \neg \mathrm{P}\) è vera. Questo mostra che le espressioni \(\mathrm{P}\) e \(\neg\neg \mathrm{P}\) sono equivalenti, ovvero che vale la
Legge della doppia negazione \[\mathrm{P} \equiv \neg \neg \mathrm{P}.\]
Inoltre
\(\mathrm{P}\equiv\mathrm{Q}\) se e solo se \(\neg\mathrm{P}\equiv\neg\mathrm{Q}\).
Infatti, in qualunque contesto si ha che se \(\mathrm{P}\equiv\mathrm{Q}\) allora
| \( \neg\mathrm{P} \text{ è vero} \) | \( \text{se e solo se} \mathrm{P} \text{ è falso} \) |
| \( \text{se e solo se} \mathrm{Q} \text{è falso} \) | |
| \( \text{se e solo se} \neg\mathrm{Q}\text{ è vero.} \) |
\(\wedge\) è la congiunzione e serve per asserire che due fatti valgono contemporaneamente.
Per esempio
( \(x\) è pari ) \(\wedge\) ( \(x\) è un quadrato perfetto)
significa che il numero \(x\) è sia pari che un quadrato perfetto (ovvero è il quadrato di qualche numero): poiché abbiamo dimostrato che se \(k^2\) è pari allora anche \(k\) lo è, questo vuol dire che \(x = (2n)^2 = 4n^2\) per qualche \(n \in \mathbb{N}\).
Anche le particelle “ma” e “però” sono delle congiunzioni, a cui noi attribuiamo una connotazione avversativa. Tuttavia, in matematica il significato di “\(\mathrm{P}\) ma \(\mathrm{Q}\)” o di “\(\mathrm{P}\) però \(\mathrm{Q}\)” è lo stesso di “\(\mathrm{P}\) e \(\mathrm{Q}\)” e quindi si scrivono comunque come “\(\mathrm{P} \wedge \mathrm{Q}\)”.
Il connettivo \(\wedge\) è commutativo, poiché asserire \(\mathrm{P} \wedge \mathrm{Q}\) è come asserire \(\mathrm{Q}\wedge \mathrm{P}\), in simboli
\(\mathrm{P} \wedge \mathrm{Q}\equiv \mathrm{Q}\wedge \mathrm{P}\),
ed è associativo, poiché asserire \(\mathrm{P} \wedge (\mathrm{Q} \wedge \mathrm{R})\) è la stessa cosa di asserire \((\mathrm{P} \wedge \mathrm{Q}) \wedge \mathrm{R}\) (ovvero: \(\mathrm{P}\), \(\mathrm{Q}\) ed \(\mathrm{R}\) sono tutt’e tre vere), in simboli
\(\mathrm{P} \wedge (\mathrm{Q} \wedge \mathrm{R}) \equiv (\mathrm{P} \wedge \mathrm{Q}) \wedge \mathrm{R}\).
È chiaro che in qualunque contesto ci troviamo, se \(\mathrm{P}\) e \(\mathrm{Q}\) sono vere allora anche \(\mathrm{P} \wedge \mathrm{Q}\) lo è, in simboli
\(\mathrm{P},\mathrm{Q} \models\mathrm{P}\wedge \mathrm{Q}\).
Viceversa, se \(\mathrm{P} \wedge \mathrm{Q}\) è un’affermazione vera, allora lo sono in particolare sia \(\mathrm{P}\) che \(\mathrm{Q}\), in simboli possiamo scrivere che
\(\mathrm{P}\wedge\mathrm{Q} \models\mathrm{P}\) e \(\mathrm{P}\wedge\mathrm{Q} \models\mathrm{Q}\) .
Infine
Se \(\mathrm{P}\equiv \mathrm{R}\) e \(\mathrm{Q}\equiv \mathrm{S}\), allora \(\mathrm{P}\wedge\mathrm{Q} \equiv \mathrm{R}\wedge\mathrm{S}\).
Infatti se siamo in un contesto in cui vale \(\mathrm{P}\wedge\mathrm{Q}\), in tale contesto devono necessariamente valere sia \(\mathrm{P}\) che \(\mathrm{Q}\). Dato che \(\mathrm{P} \models \mathrm{R}\) e \(\mathrm{Q} \models \mathrm{S}\), in tale contesto varranno sia \(\mathrm{R}\) che \(\mathrm{S}\), da cui concludiamo che varrà anche \(\mathrm{R}\wedge\mathrm{S}\).
Il ragionamento mostra che in ogni contesto in cui vale \(\mathrm{P}\wedge\mathrm{Q}\) vale anche \(\mathrm{R}\wedge\mathrm{S}\), per cui
\(\mathrm{P}\wedge\mathrm{Q} \models \mathrm{R}\wedge\mathrm{S}\)
In maniera simile si dimostra \(\mathrm{R} \wedge \mathrm{S} \models \mathrm{P} \wedge \mathrm{Q}\), da cui
\(\mathrm{P} \wedge \mathrm{Q} \equiv \mathrm{R} \wedge \mathrm{S}\).
\(\vee\) è la disgiunzione (inclusiva) e corrisponde al vel latino o all’inglese or: questo o quello o eventualmente entrambi.
In particolare, affermare che vale \(\mathrm{P} \vee \mathrm{Q}\) non vuol dire che soltanto una tra \(\mathrm{P}\) e \(\mathrm{Q}\) è vera. Se asseriamo ad esempio che
( \(x\) è pari ) \(\vee\) ( \(x\) è un quadrato perfetto)
intendiamo dire che il numero \(x\) può essere pari (cioè della forma \(2n\), per esempio \(6\)), o un quadrato perfetto (cioè della forma \(n^2\), per esempio \(9\)), o magari un numero che è un quadrato perfetto pari (cioè della forma \(4 n^2\), per esempio \(4\)).
Anche il connettivo \(\vee\) è commutativo, poiché \(\mathrm{P}\vee \mathrm{Q}\) ha lo stesso significato di \(\mathrm{Q}\vee \mathrm{P}\), in simboli
\(\mathrm{P}\vee \mathrm{Q}\equiv\mathrm{Q}\vee \mathrm{P}\),
e associativo, poiché \(\mathrm{P} \vee (\mathrm{Q} \vee \mathrm{R})\) ha lo stesso significato di \((\mathrm{P}\vee \mathrm{Q}) \vee \mathrm{R}\) (ovvero: almeno una tra \(\mathrm{P}\), \(\mathrm{Q}\) ed \(\mathrm{R}\) è vera), in simboli
\(\mathrm{P} \vee (\mathrm{Q} \vee \mathrm{R}) \equiv (\mathrm{P}\vee \mathrm{Q}) \vee \mathrm{R}\).
Se sappiamo che una certa affermazione \(\mathrm{P}\) è vera, allora possiamo anche asserire che \(\mathrm{P} \vee \mathrm{Q}\) è vera, qualsiasi sia l’affermazione \(\mathrm{Q}\); infatti, \(\mathrm{P} \vee \mathrm{Q}\) è vera quando è vera almeno una delle due affermazioni \(\mathrm{P}\) e \(\mathrm{Q}\), e nel nostro caso \(\mathrm{P}\) lo è. Viceversa, se \(\mathrm{Q}\) è vera allora anche \(\mathrm{P} \vee \mathrm{Q}\) lo è, qualunque sia \(\mathrm{P}\). Quindi
\(\mathrm{P} \models \mathrm{P}\vee \mathrm{Q}\) e \(\mathrm{Q} \models\mathrm{P}\vee \mathrm{Q}\).
Invece a partire da \(\mathrm{P}\vee \mathrm{Q}\) non possiamo né concludere \(\mathrm{P}\) né concludere \(\mathrm{Q}\). Infatti, se \(\mathrm{P} \vee \mathrm{Q}\) è vera sappiamo solo che almeno una tra \(\mathrm{P}\) e \(\mathrm{Q}\) è vera, ma non possiamo sapere quale (in genere dipenderà dal contesto).
Invece, se sappiamo che \(\mathrm{P}\vee \mathrm{Q}\) è vera ma che \(\mathrm{P}\) è falsa, allora l’unica possibilità è che \(\mathrm{Q}\) sia vera (se \(\mathrm{P}\) e \(\mathrm{Q}\) fossero entrambe false, sarebbe falsa anche \(\mathrm{P} \vee \mathrm{Q}\)). Similmente, se \(\mathrm{P} \vee \mathrm{Q}\) è vera ma \(\mathrm{Q}\) è falsa, allora possiamo concludere che \(\mathrm{P}\) deve essere vera. Questa è la
Legge della disgiunzione \(\mathrm{P}\vee \mathrm{Q}, \neg \mathrm{P}\models \mathrm{Q}\) e \(\mathrm{P}\vee \mathrm{Q}, \neg \mathrm{Q}\models\mathrm{P}.\)
Infine
Se \(\mathrm{P}\equiv \mathrm{R}\) e \(\mathrm{Q}\equiv \mathrm{S}\), allora \(\mathrm{P}\vee\mathrm{Q} \equiv \mathrm{R}\vee\mathrm{S}\) .
Infatti se vale \(\mathrm{P} \vee \mathrm{Q}\), allora certamente almeno una tra \(\mathrm{P}\) e \(\mathrm{Q}\) vale. Nel primo caso (\(\mathrm{P}\) è vera), poiché \(\mathrm{P} \models \mathrm{R}\) e \(\mathrm{R} \models \mathrm{R} \vee \mathrm{S}\) si ottiene per composizione che deve valere \(\mathrm{R} \vee \mathrm{S}\). Nel secondo caso (\(\mathrm{Q}\) è vera), poiché \(\mathrm{Q} \models \mathrm{S}\) e \(\mathrm{S} \models \mathrm{R} \vee \mathrm{S}\) si ottiene nuovamente \(\mathrm{R} \vee \mathrm{S}\). Quindi in ogni caso si ha che vale \(\mathrm{R} \vee \mathrm{S}\), ovvero
\(\mathrm{P} \vee \mathrm{Q} \models \mathrm{R} \vee \mathrm{S}\).
Similmente si dimostra
\(\mathrm{R} \vee \mathrm{S} \models \mathrm{P} \vee \mathrm{Q}\),
da cui
\(\mathrm{P} \vee \mathrm{Q} \equiv \mathrm{R} \vee \mathrm{S}\).
Combinando quanto visto finora riguardo ai connettivi \(\neg\), \(\wedge\) e \(\vee\), possiamo già fare alcune osservazioni interessanti. Ad esempio, possiamo argomentare che valgono le
Leggi di De Morgan \(\neg ( \mathrm{P} \wedge \mathrm{Q}) \equiv \neg \mathrm{P} \vee \neg \mathrm{Q}\) e \(\neg (\mathrm{P} \vee \mathrm{Q}) \equiv \neg \mathrm{P} \wedge \neg \mathrm{Q}\) .
Infatti, se sappiamo che \(\mathrm{P} \wedge \mathrm{Q}\) è falsa, allora almeno una tra \(\mathrm{P}\) e \(\mathrm{Q}\) deve essere falsa: questo mostra che \(\neg (\mathrm{P} \wedge \mathrm{Q}) \models \neg \mathrm{P} \vee\neg \mathrm{Q}\).
Viceversa, se sappiamo che almeno una tra \(\mathrm{P}\) e \(\mathrm{Q}\) è certamente falsa, allora \(\mathrm{P} \wedge \mathrm{Q}\) è anch’essa falsa: questo dimostra che \(\neg \mathrm{P} \vee \neg\mathrm{Q} \models \neg (\mathrm{P} \wedge \mathrm{Q})\) ,
da cui \(\neg (\mathrm{P} \wedge \mathrm{Q}) \equiv \neg \mathrm{P} \vee \neg \mathrm{Q}\).
Lasciamo al lettore il verificare con ragionamenti analoghi che \(\neg (\mathrm{P} \vee \mathrm{Q}) \equiv \neg \mathrm{P} \wedge \neg \mathrm{Q}\).
Negando entrambi i termini dell’equivalenza \(\neg ( \mathrm{P} \wedge \mathrm{Q}) \equiv \neg \mathrm{P} \vee \neg \mathrm{Q}\) si ottiene, sfruttando quanto visto per la \(\neg\), che
\(\neg \neg ( \mathrm{P} \wedge \mathrm{Q}) \equiv \neg (\neg \mathrm{P} \vee \neg \mathrm{Q})\),
da cui per la legge della doppia negazione
\(\mathrm{P} \wedge \mathrm{Q} \equiv \neg (\neg \mathrm{P} \vee \neg \mathrm{Q})\).
Questo vuol dire che la congiunzione \(\wedge\) può essere “definita” a partire da negazione \(\neg\) e disgiunzione \(\vee\): ogni affermazione che contenga una congiunzione potrebbe essere riscritta in maniera equivalente utilizzando al suo posto negazioni e disgiunzioni in modo opportuno.
Similmente, partendo da \(\neg (\mathrm{P} \vee \mathrm{Q}) \equiv \neg \mathrm{P} \wedge \neg \mathrm{Q}\) e ragionando come prima si verifica che
\(\mathrm{P} \vee \mathrm{Q} \equiv \neg (\neg \mathrm{P} \wedge \neg \mathrm{Q})\),
ovvero che la disgiunzione \(\vee\) può essere “definita” a partire da negazione \(\neg\) e congiunzione \(\wedge\).
Valgono poi la proprietà distributiva di \(\vee\) su \(\wedge\)
\(\mathrm{P} \vee (\mathrm{Q} \wedge \mathrm{R}) \equiv (\mathrm{P} \vee \mathrm{Q}) \wedge (\mathrm{P} \vee \mathrm{R})\).
e la proprietà distributiva di \(\wedge\) su \(\vee\)
\(\mathrm{P} \wedge (\mathrm{Q} \vee \mathrm{R}) \equiv (\mathrm{P} \wedge \mathrm{Q}) \vee (\mathrm{P} \wedge \mathrm{R})\).
Per la simmetria di \(\vee\) e \(\wedge\) si avrà anche
\((\mathrm{P} \wedge \mathrm{Q}) \vee \mathrm{R} \equiv (\mathrm{P} \vee \mathrm{R}) \wedge (\mathrm{Q} \vee \mathrm{R})\) e \((\mathrm{P} \vee \mathrm{Q}) \wedge \mathrm{R} \equiv (\mathrm{P} \wedge \mathrm{R}) \vee (\mathrm{Q} \wedge \mathrm{R})\).
La dimostrazione di queste proprietà non è del tutto immediata: per questa ragione verrà posticipata alla Sezione 1.3 dove, utilizzando le tavole di verità, potremo controllarne in modo assai più semplice la validità.
\(\mathrm{P} \vee \neg \mathrm{P}\)
è sempre vera, qualunque sia \(\mathrm{P}\). Infatti, dato un qualunque contesto si ha che in esso o \(\mathrm{P}\) è vera oppure \(\mathrm{P}\) è falsa: nel primo caso si ottiene che \(\mathrm{P} \vee \neg \mathrm{P}\) è vera poiché \(\mathrm{P} \models \mathrm{P} \vee \neg \mathrm{P}\), nel secondo caso si ottiene nuovamente che \(\mathrm{P} \vee \neg \mathrm{P}\) è vera poiché \(\neg \mathrm{P} \models \mathrm{P} \vee \neg \mathrm{P}\).
Affermazioni come \(\mathrm{P} \vee \neg \mathrm{P}\), ovvero affermazioni che sono sempre vere, indipendentemente dal contesto, verranno chiamate tautologie. In simboli, scriviamo \[\models \mathrm{Q}\] per dire che \(\mathrm{Q}\) è una tautologia.
Contraddizioni
Siccome \(\mathrm{P} \vee \neg \mathrm{P}\) è sempre vera, la sua negazione \(\neg (\mathrm{P} \vee \neg \mathrm{P})\) è sempre falsa. Poiché per le leggi di De Morgan \[\neg (\mathrm{P} \vee \neg \mathrm{P}) \equiv \neg \mathrm{P} \wedge \neg \neg \mathrm{P}\] e per la legge della doppia negazione \[\neg \mathrm{P} \wedge \neg \neg \mathrm{P} \equiv \neg \mathrm{P} \wedge \mathrm{P}\] applicando la simmetria di \(\wedge\) all’ultima espressione otteniamo che
\(\mathrm{P} \wedge \neg \mathrm{P}\)
è sempre falsa, qualunque sia \(\mathrm{P}\).
Affermazioni di questo tipo, ovvero affermazioni che sono sempre false, indipendentemente dal contesto, verranno chiamate contraddizioni.
Si può anche osservare che \[\mathrm{Q} \models \mathrm{P} \vee \neg \mathrm{P},\] qualunque siano \(\mathrm{P}\) e \(\mathrm{Q}\). Infatti asserire \(\mathrm{Q} \models \mathrm{P} \vee \neg \mathrm{P}\) significa dire che: “in ogni conteso in cui vale \(\mathrm{Q}\), vale anche \(\mathrm{P} \vee \neg \mathrm{P}\)”. Ma poiché, \(\mathrm{P}\vee \neg \mathrm{P}\) è sempre vera, sarà in particolare vera anche nei contesti in cui vale \(\mathrm{Q}\). Quindi abbiamo verificato che effettivamente \(\mathrm{Q} \models \mathrm{P} \vee \neg \mathrm{P}\). Ovviamente \(\mathrm{P} \vee \neg \mathrm{P}\) potrebbe essere sostituita da qualunque altra tautologia.
Viceversa, \[\mathrm{P} \wedge \neg \mathrm{P} \models \mathrm{Q},\] indipendentemente da \(\mathrm{P}\) e \(\mathrm{Q}\). Infatti, poiché non accade mai che \(\mathrm{P} \wedge \neg \mathrm{P}\) sia vera, allora è vero che “in ogni contesto in cui vale \(\mathrm{P} \wedge \neg \mathrm{P}\), vale anche \(\mathrm{Q}\)” (semplicemente non c’è nessun contesto in cui si deve necessariamente verificare \(\mathrm{Q}\)). Ovviamente \(\mathrm{P} \wedge \neg \mathrm{P}\) potrebbe essere sostituita da qualunque contraddizione. Questo è il cosiddetto principio dell’ex falso quodlibet.
\(\rightarrow\) è l’implicazione e corrisponde all’espressione “se …allora …”.
Precisare il significato dell’implicazione è piuttosto delicato ed è il primo scoglio in cui ci si imbatte quando si formalizza il ragionamento matematico. Infatti, se sappiamo che è vero che “Se vale \(\mathrm{P}\) allora vale \(\mathrm{Q}\)”, allora saremo tutti concordi nel ritenere che in ogni contesto in cui \(\mathrm{P}\) sia vera, si debba avere che anche \(\mathrm{Q}\) è vera. Ma cosa dire dei contesti in cui \(\mathrm{P}\) risulta falsa? Se ad esempio nel nostro contesto sia \(\mathrm{P}\) che \(\mathrm{Q}\) sono false, siamo ancora disposti a ritenere la frase “Se vale \(\mathrm{P}\) allora vale \(\mathrm{Q}\)” vera?
Per chiarire la situazione, cominciamo con un esempio. Consideriamo la seguente affermazione riguardante un generico numero reale \(x\).
Se \(\underbrace{x > 0}_{\mathrm{P}}\) allora \(\underbrace{x = y^2 \text{ per qualche } y \geq 0}_{\mathrm{Q}}\).
Tale frase è chiaramente vera in ogni contesto in cui abbia senso valutarla: infatti, per ogni numero reale \(x\) se vale \(\mathrm{P}\), ovvero \(x > 0\), allora basta porre \(y = \sqrt{x}\) per avere che anche \(\mathrm{Q}\) vale. Notiamo che anche nei contesti in cui \(x \leq 0\), ovvero quando \(\mathrm{P}\) è falsa, non possiamo ritenere l’affermazione precedente errata: semplicemente diremmo che in quel caso non c’è nulla da verificare perché l’affermazione impone vincoli solo per gli \(x> 0\) (in particolare, è ininfluente se \(\mathrm{Q}\) sia vera o meno in tale contesto). In altre parole:
L’affermazione “Se \(\mathrm{P}\) allora \(\mathrm{Q}\)” precedente risulterebbe falsa in un dato contesto, ovvero per un dato valore di \(x\), solo se si verificasse che \(x > 0\) (“\(\mathrm{P}\) vera”) ma \(x\) non fosse il quadrato di un numero positivo (“\(\mathrm{Q}\) falsa”).
Proviamo ora a considerare quest’altra affermazione riguardante un generico numero reale \(x\).
Se \(\underbrace{x > 0}_{\mathrm{P}}\) allora \(\underbrace{x^2 > 1}_{\mathrm{Q}}\).
Anche questa frase è della forma “Se \(\mathrm{P}\) allora \(\mathrm{Q}\)”, ma questa volta non saremo disposti a ritenerla vera in generale: più precisamente, noteremo che ci sono alcuni contesti in cui essa vale (ad esempio quando \(x > 1\)) e contesti in cui essa non vale. Questi ultimi sono esattamente quelli dati dai valori di \(x\) per cui accade che \(x > 0\) (“\(\mathrm{P}\) vera”) ma \(x^2 \leq 1\) (“\(\mathrm{Q}\) falsa”), ovvero i contesti in cui \(0 < x \leq 1\).
Vediamo un ultimo esempio. La frase della forma \(\mathrm{P} \to \mathrm{Q}\)
Se \(\underbrace{\text{\emph{piove}}}_{\mathrm{P}}\) allora \(\underbrace{\text{\emph{in cielo ci sono le nuvole}}}_{\mathrm{Q}}\).
è chiaramente vera in ogni possibile contesto: in ogni possibile situazione, se sta effettivamente piovendo allora certamente ci devono anche essere delle nuvole in cielo da cui la pioggia cade. In altre parole, in qualunque contesto l’implicazione \(\mathrm{P} \to \mathrm{Q}\) considerata è vera perché o non sta piovendo, oppure se sta piovendo allora necessariamente ci sono delle nuvole in cielo. Viceversa, l’affermazione
Se \(\underbrace{\text{\emph{in cielo ci sono le nuvole}}}_{\mathrm{Q}}\) allora \(\underbrace{\text{\emph{piove}}}_{\mathrm{P}}\).
è falsa in determinati contesti, ovvero quando accade che ci sia una giornata nuvolosa (“\(\mathrm{Q}\) vera”) ma senza pioggia (“\(\mathrm{P}\) falsa”). Quindi l’implicazione \(\mathrm{Q} \to \mathrm{P}\) non può essere ritenuta vera in generale.
Riassumendo quanto discusso finora, abbiamo quindi che
L’affermazione \(\mathrm{P} \to \mathrm{Q}\) è falsa in un dato contesto se e solo se in tale contesto accade che \(\mathrm{P}\) è vera ma \(\mathrm{Q}\) è falsa, ovvero se in esso vale \(\mathrm{P} \wedge \neg \mathrm{Q}\).
Di conseguenza, \(\mathrm{P} \to \mathrm{Q}\) è vera in un dato contesto se e solo se in tale contesto non vale \(\mathrm{P} \wedge \neg \mathrm{Q}\); equivalentemente, se in esso vale \(\neg \mathrm{P} \vee \mathrm{Q}\).
Infatti i nostri ragionamenti evidenziano che
\(\neg(\mathrm{P} \to \mathrm{Q}) \equiv \mathrm{P} \wedge \neg \mathrm{Q}\) e \(\mathrm{P} \to \mathrm{Q} \equiv \neg (\mathrm{P} \wedge \neg \mathrm{Q})\).
Dalla seconda equivalenza, per le leggi di De Morgan e della doppia negazione
\(\mathrm{P} \to \mathrm{Q} \equiv \neg \mathrm{P} \vee \mathrm{Q}\).
In particolare, questo vuol dire che l’implicazione può essere “definita” a partire da negazione e congiunzione, oppure a partire da negazione e disgiunzione.
In accordo con la nostra intuizione, il significato dato all’implicazione cattura quello di conseguenza logica:
\(\mathrm{P}\models \mathrm{Q}\) se e solo se \(\models \mathrm{P}\rightarrow \mathrm{Q}\).
Infatti, supponiamo che \(\mathrm{P} \models \mathrm{Q}\). Allora in ogni contesto in cui vale \(\mathrm{P}\) deve valere anche \(\mathrm{Q}\): in particolare, in nessun contesto può valere \(\mathrm{P} \wedge \neg \mathrm{Q}\), per cui \(\models \neg (\mathrm{P} \wedge \neg \mathrm{Q})\). Poiché \(\neg( \mathrm{P} \wedge \neg \mathrm{Q}) \equiv \mathrm{P} \to \mathrm{Q}\), abbiamo \(\models \mathrm{P} \to \mathrm{Q}\).
Viceversa, supponiamo che \(\models \mathrm{P} \to \mathrm{Q}\), ovvero che l’implicazione \(\mathrm{P} \to \mathrm{Q}\) sia vera in qualunque contesto. Supponiamo di trovarci in un contesto in cui vale \(\mathrm{P}\), cosicché vale anche \(\neg \neg \mathrm{P}\) per la legge della doppia negazione. Siccome \(\mathrm{P} \to \mathrm{Q} \equiv \neg \mathrm{P} \vee \mathrm{Q}\), in tale contesto deve valere anche \(\neg \mathrm{P} \vee \mathrm{Q}\). Per la legge della disgiunzione applicata a \(\neg \mathrm{P} \vee \mathrm{Q}\) e \(\neg \neg P\), si ha allora che \(\mathrm{Q}\) vale in tale contesto. Quindi abbiamo verificato che \(\mathrm{P} \models \mathrm{Q}\).
Più in generale, ricordiamo che \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\) se in ogni contesto in cui tutte le \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sono vere si ha che anche \(\mathrm{Q}\) è vera. Poiché in ogni contesto si ha che \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sono tutte vere se e solo se è vera \(\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}\), allora
\(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\)
se e solo se
\(\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n} \models \mathrm{Q}\)
se e solo se
\(\models \mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n} \to \mathrm{Q}\).
In matematica, si usano anche altre espressioni che sono equivalenti all’implicazione.
Le espressioni “affinché valga \(\mathrm{P}\) deve valere \(\mathrm{Q}\)” oppure “affinché valga \(\mathrm{P}\) è necessario che valga \(\mathrm{Q}\)” significano che non può accadere che \(\mathrm{P}\) valga ma \(\mathrm{Q}\) no. Il loro significato è quindi equivalente a quello di “se \(\mathrm{P}\) allora \(\mathrm{Q}\)” e perciò si scrivono, in simboli, \(\mathrm{P} \rightarrow \mathrm{Q}\).
L’espressione “affinché valga \(\mathrm{P}\) è sufficiente che valga \(\mathrm{Q}\)” significa che non appena si sa che \(\mathrm{Q}\) vale, allora anche \(\mathrm{P}\) deve valere. Il suo significato è quindi equivalente a quello di “se \(\mathrm{Q}\) allora \(\mathrm{P}\)” e perciò si scrive, in simboli, \(\mathrm{Q} \rightarrow \mathrm{P}\).
Osservazione L’implicazione cattura il concetto intuitivo di conseguenza. Diciamo che \(\mathrm{Q}\) è una conseguenza di \(\mathrm{P}\) se ogni volta che si verifica \(\mathrm{P}\) allora anche \(\mathrm{Q}\) si deve verificare, ovvero \(\mathrm{P} \to \mathrm{Q}\).
L’implicazione non ha invece nulla a che fare con il concetto di causalità. Infatti, si ritiene usualmente che \(\mathrm{P}\) sia una causa di \(\mathrm{Q}\) se è una condicio sine qua non, ovvero se non può accadere \(\mathrm{Q}\) senza che si verifichi \(\mathrm{P}\). Questo vuol dire che se c’è un nesso di causalità tra \(\mathrm{P}\) e \(\mathrm{Q}\), allora l’unica cosa che possiamo affermare è che \(\mathrm{Q} \to \mathrm{P}\); non possiamo invece affermare che \(\mathrm{P} \to \mathrm{Q}\), perché non possiamo asserire con certezza che \(\mathrm{P}\) sia sufficiente, da sola, a causare \(\mathrm{Q}\) (potrebbero essere necessarie altre concause affinché si verifichi veramente \(\mathrm{Q}\)).
C’è poi un’ultimo aspetto di cui tener conto. A differenza di quanto accade per i concetti intuitivi di “conseguenza” e “causa”, è possibile valutare se è vero che \(\mathrm{P} \to \mathrm{Q}\) anche quando \(\mathrm{P}\) e \(\mathrm{Q}\) sono affermazioni che non hanno nulla a che fare una con l’altra.
Ad esempio se \(\mathrm{P}\) è l’affermazione
Il ghiaccio ha una temperatura di 100 gradi centigradi.
e \(\mathrm{Q}\) è l’affermazione
L’Empoli vincerà il campionato di calcio nel 2028.
allora si può comunque ritenere l’implicazione \(\mathrm{P} \to \mathrm{Q}\) vera (poiché non può certamente verificarsi che \(\mathrm{P}\) valga ma \(\mathrm{Q}\) no, essendo che \(\mathrm{P}\) è sempre falsa), anche se evidentemente non c’è nessuna relazione di “conseguenza” o “causalità” tra \(\mathrm{P}\) e \(\mathrm{Q}\) nel senso intuitivo di tali termini.
Il connettivo \(\to\) non è affatto commutativo: \(\mathrm{P} \to \mathrm{Q}\) e \(\mathrm{Q} \to \mathrm{P}\) hanno significati completamente diversi!
Infatti, se ad esempio \(\mathrm{Q}\) è vera e \(\mathrm{P}\) è falsa, allora l’implicazione \(\mathrm{P} \to \mathrm{Q}\) risulterà vera, mentre l’implicazione \(\mathrm{Q} \to \mathrm{P}\) risulterà falsa. Dunque queste due implicazioni non sono equivalenti.
Si verifica anche che \(\to\) non è associativo, ovvero che \(\mathrm{P} \to (\mathrm{Q} \to \mathrm{R} )\) e \((\mathrm{P} \to \mathrm{Q}) \to \mathrm{R}\) non sono espressioni equivalenti.
Infatti, se ad esempio sia \(\mathrm{P}\) che \(\mathrm{R}\) sono false, allora è facile verificare che \(\mathrm{P} \to ( \mathrm{Q} \to \mathrm{R})\) è vera, mentre \((\mathrm{P} \to \mathrm{Q}) \to \mathrm{R}\) è falsa (indipendentemente dal fatto che \(\mathrm{Q}\) sia vera o meno).
L’implicazione \(\mathrm{P} \to \mathrm{Q}\) è invece equivalente al suo contrappositivo \(\neg \mathrm{Q} \to \neg \mathrm{P}\), in simboli
\(\mathrm{P} \to \mathrm{Q} \equiv \neg \mathrm{Q} \to \neg \mathrm{P}\).
Infatti per la legge della doppia negazione e la simmetria di \(\vee\) si ha
\(\mathrm{P} \to \mathrm{Q}\) \(\equiv \neg \mathrm{P} \vee \mathrm{Q}\)
\(\equiv \neg \mathrm{P} \vee \neg \neg \mathrm{Q}\)
\(\equiv \neg \neg \mathrm{Q} \vee \neg \mathrm{P}\)
\(\equiv \neg \mathrm{Q}\to \neg \mathrm{P}\).
Infine
Se \(\mathrm{P}\equiv \mathrm{R}\) e \(\mathrm{Q}\equiv \mathrm{S}\), allora \(\mathrm{P}\rightarrow\mathrm{Q} \equiv \mathrm{R}\rightarrow\mathrm{S}\) .
Infatti, utilizzando quanto visto per negazione e disgiunzione si ha
\(\mathrm{P} \to \mathrm{Q}\) \(\equiv \neg \mathrm{P} \vee \mathrm{Q}\)
\(\equiv \neg \mathrm{R} \vee \mathrm{S}\)
\(\equiv \mathrm{R} \to \mathrm{S}\).
Dall’equivalenza \(\mathrm{P} \to \mathrm{Q} \equiv \neg \mathrm{P} \vee \mathrm{Q}\) si può anche ricavare una delle più famose tra le leggi logiche, ovvero il
Modus Ponens \(\mathrm{P} \to \mathrm{Q}, \mathrm{P}\) \(\models\) \(\mathrm{Q}\) .
Infatti, se siamo in un contesto in cui vale \(\mathrm{P} \to \mathrm{Q}\), allora vale anche \(\neg \mathrm{P} \vee \mathrm{Q}\). Se inoltre vale anche \(\mathrm{P}\), per la legge della doppia negazione vale anche \(\neg \neg \mathrm{P}\). Applicando la legge della disgiunzione, concludiamo che deve valere \(\mathrm{Q}\).
\(\leftrightarrow\) è la bi-implicazione e corrisponde all’espressione “…se e solo se …”.
Quando asseriamo che “\(\mathrm{P}\) se e solo se \(\mathrm{Q}\)” intendiamo dire che “se \(\mathrm{P}\) allora \(\mathrm{Q}\), e se \(\mathrm{Q}\) allora \(\mathrm{P}\)”. In altre parole, \(\mathrm{P} \leftrightarrow \mathrm{Q}\) è equivalente ad affermare \[(\mathrm{P} \to \mathrm{Q}) \wedge (\mathrm{Q} \to \mathrm{P}).\]
In particolare, \(\mathrm{P} \leftrightarrow \mathrm{Q}\) è vera se e solo se in ogni contesto si verifica che o \(\mathrm{P}\) e \(\mathrm{Q}\) sono entrambe vere, oppure sono entrambe false.
Spesso in matematica “\(\mathrm{P}\) se e solo se \(\mathrm{Q}\)” lo si scrive come: “condizione necessaria e sufficiente affinché valga \(\mathrm{P}\), è che valga \(\mathrm{Q}\)”.
Utilizzando la commutatività della congiunzione e il fatto che \(\mathrm{P} \leftrightarrow \mathrm{Q} \equiv (\mathrm{P} \to \mathrm{Q}) \wedge (\mathrm{Q} \to \mathrm{P})\), si ottiene facilmente che la bi-implicazione è commutativa, ovvero
\(\mathrm{P} \leftrightarrow \mathrm{Q} \equiv \mathrm{Q} \leftrightarrow \mathrm{P}\).
Si può anche dimostrare che la bi-implicazione è associativa, ovvero
\(\mathrm{P} \leftrightarrow (\mathrm{Q} \leftrightarrow \mathrm{R}) \equiv (\mathrm{P} \leftrightarrow \mathrm{Q}) \leftrightarrow \mathrm{R}\).
Tuttavia la verifica di questo fatto è tutt’altro che banale e verrà posticipata alla Sezione 1.3, quando sapremo utilizzare le tavole di verità.
Utilizzando l’equivalenza \(\mathrm{P} \leftrightarrow \mathrm{Q} \equiv (\mathrm{P} \to \mathrm{Q}) \wedge (\mathrm{Q} \to \mathrm{P})\) e le leggi viste per la congiunzione si ha che
\(\mathrm{P} \leftrightarrow \mathrm{Q}\models \mathrm{P} \rightarrow \mathrm{Q}\) e \(\mathrm{P} \leftrightarrow \mathrm{Q}\models\mathrm{Q} \rightarrow \mathrm{P}\).
e
\(\mathrm{P} \rightarrow \mathrm{Q}, \mathrm{Q}\rightarrow \mathrm{P}\models \mathrm{P} \leftrightarrow \mathrm{Q}\).
Infine, utilizzando le analoghe leggi riguardanti implicazione e congiunzione, si verifica facilmente che
Se \(\mathrm{P} \equiv \mathrm{R}\) e \(\mathrm{Q} \equiv \mathrm{S}\), allora \(\mathrm{P} \leftrightarrow \mathrm{Q} \equiv \mathrm{R} \leftrightarrow \mathrm{S}\).
Osserviamo infine che il bicondizionale cattura il concetto di equivalenza logica, ovvero che
\(\mathrm{P}\equiv\mathrm{Q}\) se e solo se \(\models\mathrm{P} \leftrightarrow \mathrm{Q}\).
Infatti
\(\mathrm{P}\equiv\mathrm{Q}\) se e solo se
\(\mathrm{P}\models\mathrm{Q}\) e \(\mathrm{Q}\models\mathrm{P}\)
se e solo se
\(\models\mathrm{P}\to\mathrm{Q}\) e \(\models\mathrm{Q}\to\mathrm{P}\)
se e solo se
\(\models(\mathrm{P}\to\mathrm{Q})\wedge(\mathrm{Q}\to\mathrm{P})\)
se e solo se
\(\models\mathrm{P} \leftrightarrow \mathrm{Q}\).
\(\exists\) è il quantificatore esistenziale.
L’espressione \(\exists x \mathrm{P}\) si legge: “c’è un \(x\) tale che \(\mathrm{P}\)”, ovvero “l’affermazione \(\mathrm{P}\) vale per qualche \(x\)”. Essa asserisce che c’è almeno un ente (non necessariamente unico!) che gode della proprietà descritta da \(\mathrm{P}\).
\(\forall\) è il quantificatore universale.
L’espressione \(\forall x \mathrm{P}\) si legge: “per ogni \(x\) vale \(\mathrm{P}\)”, ovvero “l’affermazione \(\mathrm{P}\) vale per tutti gli \(x\)”. Essa asserisce che ogni ente gode della proprietà descritta da \(\mathrm{P}\).
Quando scriviamo un’affermazione del tipo \(\exists x \mathrm{P}\) o \(\forall x \mathrm{P}\) spesso siamo in una situazione in cui \(\mathrm{P}\) afferma qualche proprietà che l’elemento \(x\) può avere o meno.
Se \(\mathrm{P}\) è l’equazione \(x^2 + x = 0\), l’espressione \(\exists x \mathrm{P}\) dice che l’equazione data ammette una soluzione. Invece \(\forall x \mathrm{P}\) dice che ogni numero è soluzione di \(\mathrm{P}\).
Se invece \(\mathrm{P}\) non dice nulla della variabile \(x\), il significato di \(\exists x \mathrm{P}\) e di \(\forall x \mathrm{P}\) coincide con quello di \(\mathrm{P}\).
Le espressioni \(\exists x \exists y \left ( y^2 + y = 0 \right )\) e \(\forall x \exists y \left ( y^2 + y = 0 \right )\) sono entrambe equivalenti a \(\exists y \left ( y^2 + y = 0 \right )\): tutte e tre asseriscono che l’equazione \(y^2 + y = 0\) ammette una soluzione.
La negazione di espressioni che iniziano con un quantificatore è un altro dei punti che può trarre in inganno se non si presta abbastanza attenzione al significato di ciò che si sta dicendo.
La frase
Non tutti i politici sono onesti.
(che è della forma \(\neg \forall x \mathrm{P}(x)\), dove \(\mathrm{P}(x)\) significa “\(x\) è onesto”), non vuol dire che
Tutti i politici sono disonesti.
(ovvero \(\forall x \neg \mathrm{P}(x)\)), bensì è equivalente a
Esiste (almeno) un politico disonesto.
(ovvero all’espressione \(\exists x \neg \mathrm{P}(x)\)).
Similmente:
L’affermazione
Non esiste un vaccino pericoloso.
(che è della forma \(\neg \exists x \mathrm{P}(x)\), dove \(\mathrm{P}(x)\) sta per “\(x\) è pericoloso”), non vuole dire che
Qualche vaccino è sicuro.
(ovvero \(\exists x \neg \mathrm{P}(x)\)), bensì è equivalente a
Tutti i vaccini sono sicuri.
(ovvero all’espressione \(\forall x \neg \mathrm{P}(x)\)).
Più in generale, negare \(\forall x \mathrm{P}\) significa dire che non tutti gli \(x\) godono della proprietà descritta da \(\mathrm{P}\), cioè c’è almeno un \(x\) per cui si può asserire \(\neg \mathrm{P}\).
Viceversa, se neghiamo \(\exists x \mathrm{P}\) allora vuol dire che non si dà il caso che ci sia un \(x\) per cui vale \(\mathrm{P}\), cioè che per ogni \(x\) deve valere \(\neg \mathrm{P}\). Quindi
\(\neg \forall x \mathrm{P} \equiv \exists x \neg \mathrm{P}\) e \(\neg \exists x \mathrm{P}\equiv \forall x \neg \mathrm{P}\).
Negando entrambi i termini di ciascuna delle equivalenze precedenti e applicando la legge della doppia negazione si ottiene
\(\forall x \mathrm{P}\equiv \neg \exists x \neg \mathrm{P}\) e \(\exists x \mathrm{P}\equiv \neg \forall x \neg \mathrm{P}\).
Questo vuol dire che ciascuno dei due quantificatori \(\forall\) e \(\exists\) può essere “definito” a partire dall’altro quantificatore e dalla negazione.
Quando scriviamo \(\forall x \forall y \mathrm{P}\) intendiamo dire che in qualsiasi modo si scelgano gli elementi \(x\) e \(y\) vale \(\mathrm{P}\), e questo è la stessa cosa che dire \(\forall y \forall x \mathrm{P}\).
Analogamente \(\exists x \exists y \mathrm{P}\) ha lo stesso significato di \(\exists y \exists x \mathrm{P}\). Quindi
\(\exists x \exists y\mathrm{P}\equiv \exists y \exists x \mathrm{P}\) e \(\forall x \forall y \mathrm{P}\equiv \forall y\forall x \mathrm{P}\).
Bisogna invece stare molto attenti quando si vuole scambiare due quantificatori di diverso tipo...
Supponiamo che valga \(\exists x \forall y \mathrm{P}\): questo vuol dire che c’è un \(\bar{x}\) tale che per ogni \(y\) vale \(\mathrm{P}\). Quindi è vero che dato un \(y\) arbitrario possiamo sempre trovare un \(x\) tale che \(\mathrm{P}\): basta prendere l’elemento \(\bar{x}\) di prima. In altre parole
\(\exists x \forall y \mathrm{P}\models\forall y \exists x \mathrm{P}.\)
Questa regola non può però essere invertita! Da \(\forall y \exists x \mathrm{P}\) non possiamo affatto concludere \(\exists x \forall y \mathrm{P}\): si considerino ad esempio le affermazioni \(\forall y \exists x ( y < x )\) e \(\exists x \forall y ( y < x )\) (nei numeri naturali, la prima è vera ma la seconda è falsa).
Questo vuol dire, in particolare, che le espressioni \(\exists x \forall y \mathrm{P}\) e \(\forall y \exists x \mathrm{P}\) non sono equivalenti: dalla prima segue la seconda, ma non viceversa.
Il quantificatore esistenziale si può distribuire e raccogliere rispetto alla disgiunzione nel seguente senso: dire che “c’è un \(x\) per cui \(\mathrm{P}\) oppure c’è un \(x\) per cui \(\mathrm{Q}\)” è equivalente a dire “c’è un \(x\) per cui \(\mathrm{P}\) o \(\mathrm{Q}\)”, in simboli
\(\left (\exists x\mathrm{P} \right ) \vee\left ( \exists x \mathrm{Q} \right )\equiv \exists x ( \mathrm{P} \vee \mathrm{Q} )\).
Rispetto alla congiunzione, invece, solo una delle due possibili regole è valida: il quantificatore si può distribuire ma non raccogliere. Infatti, se “c’è un \(x\) tale che \(\mathrm{P}\) e \(\mathrm{Q}\)” allora “c’è un \(x\) tale che \(\mathrm{P}\), e c’è un \(x\) tale che \(\mathrm{Q}\)”, in simboli
\(\exists x ( \mathrm{P}\wedge \mathrm{Q} ) \models (\exists x \mathrm{P})\wedge ( \exists x \mathrm{Q} )\).
Il viceversa però non vale: ad esempio, dal fatto che ci sia un numero naturale pari e ci sia un numero naturale dispari non possiamo concludere che esista un numero naturale che è sia pari che dispari.
Specularmente, il quantificatore universale si distribuisce e raccoglie rispetto alla congiunzione
\(\left (\forall x\mathrm{P} \right ) \wedge \left (\forall x \mathrm{Q} \right )\equiv \forall x \left (\mathrm{P} \wedge \mathrm{Q} \right )\),
ma rispetto alla disgiunzione si può raccogliere
\(\left ( \forall x \mathrm{P} \right ) \vee \left ( \forall x \mathrm{Q} \right ) \models \forall x \left (\mathrm{P}\vee \mathrm{Q} \right )\),
ma non distribuire. Ad esempio, è vero che ogni numero naturale è o pari o dispari, ma da questo non si può concludere che tutti i numeri naturali sono pari o tutti i numeri naturali sono dispari.
Questo parallelismo tra il quantificatore esistenziale e la disgiunzione, da un lato, e il quantificatore universale e la congiunzione, dall’altro, non è così sorprendente, visto che i quantificatori possono essere visti come disgiunzioni e congiunzioni generalizzate: infatti, dire che vale \(\exists x \mathrm{P} ( x )\) in \(\mathbb{N}\) equivale ad asserire \(\mathrm{P} ( 0 ) \vee \mathrm{P} ( 1 ) \vee \mathrm{P} ( 2 ) \vee \dots\), mentre dire che vale \(\forall x \mathrm{P} ( x )\) in \(\mathbb{N}\) equivale ad asserire \(\mathrm{P} ( 0 ) \wedge \mathrm{P} ( 1 ) \wedge \mathrm{P} ( 2 ) \wedge \dots\).